﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace eu.h8me.Parsing.LexerLib2 {

    /// <summary>
    /// Helper interface to compare TNFA tags.
    /// </summary>
    internal interface ITNFATag : IComparable<ITNFATag> {

        /// <summary>
        /// Accessor returning whether to match first or last occurrence of the tag (i.e., whether to use early or late
        /// match tags).
        /// </summary>
        /// <returns>Boolean indicating whether to match early.</returns>
        bool MinimizeMatch {
            get;
        }

    }

    /// <summary>
    /// Helper class to implement TNFA tags as integers (lower value, higher precedence, and explicit minimize.
    /// </summary>
    internal class TNFAIntTag : ITNFATag {

        // Data.
        private int _Tag;
        private bool _Minimize;

        /// <summary>
        /// Initialize a new TNFA integer tag bound to the specified arguments.
        /// </summary>
        /// <param name="tag">Integer tag to bind to.</param>
        /// <param name="min">Flag signalling whether to minimize this tag.</param>
        public TNFAIntTag(int tag, bool min) {
            // Store data.
            _Tag = tag;
            _Minimize = min;
        }

        /// <summary>
        /// Fetch whether we want to minimize this tag.
        /// </summary>
        public bool MinimizeMatch {
            get {
                // Return minimize flag.
                return _Minimize;
            }
        }

        /// <summary>
        /// Compare against other tag.
        /// </summary>
        /// <param name="other">Tag to compare against.</param>
        /// <returns>Comparison result.</returns>
        public int CompareTo(ITNFATag other) {
            // Convert type.
            TNFAIntTag tag = other as TNFAIntTag;
            if( tag == null )
                throw new ArgumentException("Cannot compare against other tag type than TNFAIntTag");

            // Return ID comparison result.
            return _Tag.CompareTo(tag._Tag);
        }

        /// <summary>
        /// Return string form of the current tag.
        /// </summary>
        /// <returns>String representation of tag.</returns>
        public override string ToString() {
            // Return string form.
            return String.Format("[{0}:{1}]", _Tag, _Minimize);
        }

    }

    /// <summary>
    /// Non-deterministic finite automaton with tagged epsilon transitions. Implements operators to perform merging/concatenating
    /// or repeating TNFAs, cloning the TNFA in the process.
    /// </summary>
    internal class TNFA {

        // Data.
        private TNFAState _Begin;
        private TNFAState _End;

        /// <summary>
        /// Initialize a new, empty TNFA.
        /// </summary>
        public TNFA() {
            // Initialize beginning to point to end node on epsilon transition.
            _Begin = new TNFAState();
            _End = new TNFAState();
            _Begin.EpsilonTransitions.Add(new TNFAEpsilonTransition(_End));
        }

        /// <summary>
        /// Initialize a new TNFA which carries a tagged epsilon transition, carrying the tag that is noted on the input.
        /// </summary>
        /// <param name="tag">Tag for the epsilon transition to create.</param>
        public TNFA(ITNFATag tag) {
            // Initialize a new TNFA which just contains a tagged transition.
            _Begin = new TNFAState();
            _End = new TNFAState();
            _Begin.EpsilonTransitions.Add(new TNFAEpsilonTransition(_End, tag));
        }

        /// <summary>
        /// Initialize a new TNFA which matches the specified character range.
        /// </summary>
        /// <param name="range">Character range to match in transition between states.</param>
        public TNFA(CharRange range) {
            // Initialize a new TNFA with a char range transition between them.
            _Begin = new TNFAState();
            _End = new TNFAState();
            _Begin.Transition = new TNFATransition(_End, range);
        }

        /// <summary>
        /// Initialize a new TNFA, which only has the specified beginning state bound.
        /// </summary>
        /// <param name="begin">Beginning state to bind to TNFA.</param>
        private TNFA(TNFAState begin) {
            // Only bind beginning state; rest is set up by Clone() (which is the only method to call this).
            _Begin = begin;
        }

        /// <summary>
        /// Fetch the beginning state set this TNFA is bound to.
        /// </summary>
        public TNFAState Begin {
            get {
                // Fetch the beginning state.
                return _Begin;
            }
        }

        /// <summary>
        /// Fetch the end state this TNFA is bound to.
        /// </summary>
        public TNFAState End {
            get {
                // Fetch the end state.
                return _End;
            }
        }

        /// <summary>
        /// Combine two TNFAs, producing a new TNFA which matches either the left or the right subexpression. The left
        /// subexpression receives higher priority (i.e., lower p on transitions) than the right subexpression. This function
        /// keeps the invariant that the start and end node of the resulting tree don't have incoming, resp. outgoing
        /// transitions, and that all nodes have either range or epsilon transitions coming in, never both.
        /// </summary>
        /// <param name="left">Left subexpression to match.</param>
        /// <param name="right">Right subexpression to match.</param>
        /// <returns>TNFA which matches either the left or the right subexpression.</returns>
        public static TNFA operator |(TNFA left, TNFA right) {
            // Initialize output TNFAs. The left node is preferred, and gets no priority adjustment, whereas the right node gets
            // a priority adjustment by left maximum plus 3 (to accomodate for the epsilon transition leading up to it). Finally,
            // create a new beginning (for branching) and terminal node (which merges left and right trees back together).
            TNFA rv = left.Clone(null);
            TNFA rightclone = right.Clone(null);
            TNFAState newbegin = new TNFAState();
            TNFAState newend = new TNFAState();

            // Commit epsilon transitions from left begin to right clone and from both end nodes to new end node.
            newbegin.EpsilonTransitions.Add(new TNFAEpsilonTransition(rv._Begin));
            rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(newend));
            newbegin.EpsilonTransitions.Add(new TNFAEpsilonTransition(rightclone._Begin));
            rightclone._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(newend));

            // Swap end nodes and finalize max priority of returned (left) clone.
            rv._Begin = newbegin;
            rv._End = newend;

            // Return merged.
            return rv;
        }

        /// <summary>
        /// Merge two TNFAs by concatenating them, adding an epsilon transition between the two. This function keeps the invariant
        /// that the start and end node of the resulting tree don't have incoming, resp. outgoing transitions, and that all nodes
        /// have either range or epsilon transitions coming in, never both.
        /// </summary>
        /// <param name="left">Left tree to concatenate to.</param>
        /// <param name="right">Right tree to concatenate.</param>
        /// <returns>TNFA representing the concatenation of the two subtrees.</returns>
        public static TNFA operator &(TNFA left, TNFA right) {
            // Initialize output TNFAs. The right tree gets a priority adjustment which moves it behind the left tree and the
            // binding epsilon transition.
            TNFA rv = left.Clone(null);
            TNFA rightclone = right.Clone(null);

            // Attach right clone to left and swap end nodes and finalize max priority of returned (left) clone.
            rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(rightclone._Begin));
            rv._End = rightclone._End;

            // Return merged.
            return rv;
        }

        /// <summary>
        /// Return a new TNFA which represents this TNFA, repeated one or more times. This function keeps the invariant that the
        /// start and end node of the resulting tree don't have incoming, resp. outgoing transitions, and that all nodes have
        /// either range or epsilon transitions coming in, never both.
        /// </summary>
        /// <returns>TNFA which matches the current TNFA repeated one or more times.</returns>
        public TNFA OneOrMore() {
            // Clone the TNFA without priority adjustment, and add epsilon transition from end node to front (to build loop),
            // adding two more states to keep the invariant that start doesn't have incoming and end doesn't have outgoing
            // transitions.
            TNFA rv = Clone(null);
            TNFAState newbegin = new TNFAState();
            TNFAState newend = new TNFAState();

            // Add transitions.
            newbegin.EpsilonTransitions.Add(new TNFAEpsilonTransition(rv._Begin));
            rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(rv._Begin));
            rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(newend));

            // Update start/end nodes.
            rv._Begin = newbegin;
            rv._End = newend;

            // Return merged.
            return rv;
        }

        /// <summary>
        /// Return a new TNFA which represents this TNFA, repeated zero or one time. This function keeps the invariant that the
        /// start and end node of the resulting tree don't have incoming, resp. outgoing transitions, and that all nodes have
        /// either range or epsilon transitions coming in, never both.
        /// </summary>
        /// <returns>TNFA which matches the current TNFA never or once.</returns>
        public TNFA ZeroOrOne() {
            // Clone the TNFA with priority adjustment of one and create new end node (because of the current end node possibly
            // having character range incoming transition).
            TNFA rv = Clone(null);
            TNFAState newbegin = new TNFAState();
            TNFAState newend = new TNFAState();

            // Attach transitions from beginning directly to new end, or from old end to new end, and replace end.
            newbegin.EpsilonTransitions.Add(new TNFAEpsilonTransition(rv._Begin));
            rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(newend));
            newbegin.EpsilonTransitions.Add(new TNFAEpsilonTransition(newend));

            // Update end node.
            rv._Begin = newbegin;
            rv._End = newend;

            // Return merged.
            return rv;
        }

        /// <summary>
        /// Return a new TNFA which represents this TNFA, repeated zero or more times. This function keeps the invariant that the
        /// start and end node of the resulting tree don't have incoming, resp. outgoing transitions, and that all nodes have
        /// either range or epsilon transitions coming in, never both.
        /// </summary>
        /// <returns>TNFA which matches the current TNFA zero or more times.</returns>
        public TNFA ZeroOrMore() {
            // Clone the TNFA with priority adjustment of two and create new end node (because of the current end node possibly
            // having character range incoming transition).
            TNFA rv = Clone(null);
            TNFAState newbegin = new TNFAState();
            TNFAState newend = new TNFAState();

            // Attach transitions from beginning directly to end (never), or end node to start node of clone.
            newbegin.EpsilonTransitions.Add(new TNFAEpsilonTransition(rv._Begin));
            rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(rv._Begin));
            rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(newend));
            newbegin.EpsilonTransitions.Add(new TNFAEpsilonTransition(newend));

            // Update start/end nodes.
            rv._Begin = newbegin;
            rv._End = newend;

            // Return merged.
            return rv;
        }

        /// <summary>
        /// Return a new TNFA which repeats the current TNFA the specified number of minimum up to maximum (or infinity) times.
        /// This function keeps the invariant that the start and end node of the resulting tree don't have incoming, resp.
        /// outgoing transitions, and that all nodes have either range or epsilon transitions coming in, never both.
        /// </summary>
        /// <param name="min">Minimum repeat count.</param>
        /// <param name="max">Maximum repeat count.</param>
        /// <returns>TNFA which matches the specified number of repetitions of this TNFA.</returns>
        public TNFA Repeat(int min, int? max) {
            // Check special cases.
            Debug.Assert(min >= 0 && ( !max.HasValue || max.Value >= min ), "Illegal minimum/maximum counts");
            TNFA rv = null;
            if( min == 0 ) {
                // No minimum.
                if( !max.HasValue )
                    // Zero or more, use repeat function directly.
                    return ZeroOrMore();
                else if( max.Value == 1 )
                    // Zero or one, use repeat function directly.
                    return ZeroOrOne();

                // Handle normal cases with no minimum.
                Debug.Assert(max.Value > 0, "Cannot invoke on zero total repeat count");
            } else if( min == 1 && !max.HasValue )
                // One or more, use repeat function directly.
                return OneOrMore();
            else {
                // Initialize list of clones for the min chain.
                rv = Clone(null);
                TNFAState lastbegin = rv._Begin;
                for( int i = 1; i < min; ++i ) {
                    // Create new clone which points after end.
                    TNFA clone = Clone(null);
                    rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(clone._Begin));

                    // Finalize state.
                    rv._End = clone._End;
                    lastbegin = clone._Begin;
                }

                // Check whether we have maximum repeat. If not, we just let the last element repeat.
                if( !max.HasValue ) {
                    // Create new final node for the repeat (so the end node doesn't have outgoing transitions, see the function
                    // promise above).
                    TNFAState newend = new TNFAState();

                    // Attach transitions. We never go to rv._Begin here, because that case (min==1 and !max.HasValue) is handled
                    // above, separately, so lastbegin is always somewhere inside the graph (and so we don't break the invariants).
                    rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(lastbegin));
                    rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(newend));

                    // Update transitions.
                    rv._End = newend;
                    return rv;
                } else if( max.Value == min )
                    // Max and min are equal, simply return current chain.
                    return rv;
            }

            // Initialize new stack of trailing nodes.
            Stack<TNFAState> skips = new Stack<TNFAState>();
            for( int i = min; i < max.Value; ++i ) {
                // Check whether rv is set up.
                if( rv != null ) {
                    // Create new clone node and attach it to current rv.
                    TNFA clone = Clone(null);
                    rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(clone._Begin));

                    // Push new skipping node and transition priority for it (we skip from previous end node, because that
                    // only has an epsilon transition outgoing anyway). and update new end node.
                    skips.Push(rv._End);
                    rv._End = clone._End;
               } else {
                    // Create new rv and initial skipping node.
                    rv = Clone(null);
                    TNFAState newbegin = new TNFAState();
                    newbegin.EpsilonTransitions.Add(new TNFAEpsilonTransition(rv._Begin));

                    // Push the skipping node and update return value with new beginning.
                    skips.Push(newbegin);
                    rv._Begin = newbegin;
                }
            }

            // Initialize terminal node and attach new trailing items to it.
            TNFAState finend = new TNFAState();
            while( skips.Count > 0 )
                // Fetch state and priority from stack, and attach transition.
                skips.Pop().EpsilonTransitions.Add(new TNFAEpsilonTransition(finend));

            // Finalize newend.
            rv._End.EpsilonTransitions.Add(new TNFAEpsilonTransition(finend));
            rv._End = finend;

            // Return match.
            return rv;
        }

        /// <summary>
        /// Clone the current TNFA, returning a new TNFA which incorporates the respective priority adjustment.
        /// </summary>
        /// <param name="priadj">Priority adjustment for all transitions.</param>
        /// <param name="idadj">State identity adjustment.</param>
        /// <returns>New TNFA, which is a clone of the current TNFA with the priority adjustment applied.</returns>
        public TNFA Clone(CharRange.ProcessDelegate cproc) {
            // Initialize clone. The maximum priority of the clone is adjusted accordingly.
            TNFAState beginclone = new TNFAState();
            TNFA rv = new TNFA(beginclone);

            // Initialize clone state structures.
            Dictionary<TNFAState, TNFAState> clones = new Dictionary<TNFAState, TNFAState>();
            Stack<TNFAState> toclone = new Stack<TNFAState>();
            clones[_Begin] = beginclone;
            toclone.Push(_Begin);

            // Loop while states need to be cloned.
            while( toclone.Count > 0 ) {
                // Fetch states.
                TNFAState origstate = toclone.Pop();
                TNFAState clonestate = clones[origstate];

                // Check whether the original state has a "normal" transition.
                if( origstate.Transition != null ) {
                    // Yes, clone the normal transition.
                    TNFATransition trans = origstate.Transition;
                    TNFAState clonetarget;
                    if( !clones.TryGetValue(trans.Target, out clonetarget) ) {
                        // Initialize target clone (isn't [stub]cloned yet).
                        clones[trans.Target] = clonetarget = new TNFAState();
                        toclone.Push(trans.Target);
                    }

                    // Bind new transition (processing it if opportune).
                    if( cproc != null )
                        clonestate.Transition = new TNFATransition(clonetarget, cproc(trans.Range));
                    else
                        clonestate.Transition = new TNFATransition(clonetarget, trans.Range);
                }

                // Clone epsilon transitions.
                foreach( TNFAEpsilonTransition trans in origstate.EpsilonTransitions ) {
                    // Fetch clone target.
                    TNFAState clonetarget;
                    if( !clones.TryGetValue(trans.Target, out clonetarget) ) {
                        // Initialize target clone (isn't [stub]cloned yet).
                        clones[trans.Target] = clonetarget = new TNFAState();
                        toclone.Push(trans.Target);
                    }

                    // Attach new epsilon production (and copy tag if present).
                    if( trans.HasTag )
                        clonestate.EpsilonTransitions.Add(new TNFAEpsilonTransition(clonetarget, trans.Tag));
                    else
                        clonestate.EpsilonTransitions.Add(new TNFAEpsilonTransition(clonetarget));
                }
            }

            // Finalize cloned TNFA and return it.
            rv._End = clones[_End];
            return rv;
        }

    }

    /// <summary>
    /// Helper class describing a TNFA state.
    /// </summary>
    internal class TNFAState : IComparable<TNFAState> {

        // Data.
        private static int NEXT_STATE_ID;
        private int _ID = NEXT_STATE_ID++;
        private TNFATransition _Transition;
        private List<TNFAEpsilonTransition> _EpsilonTransitions = new List<TNFAEpsilonTransition>();

        /// <summary>
        /// Create a new, uninitialized TNFA state.
        /// </summary>
        /// <param name="id">Identity of this state (unique integer).</param>
        public TNFAState() {
            // Initialize new, empty state with specified ID.
        }

        /// <summary>
        /// Access transition bound to this TNFA state.
        /// </summary>
        public TNFATransition Transition {
            get {
                // Return main transition.
                return _Transition;
            }
            set {
                // Store transition.
                Debug.Assert(_Transition == null, "Trying to replace existing transition on TNFA state");
                _Transition = value;
            }
        }

        /// <summary>
        /// Access list of epsilon transitions.
        /// </summary>
        public List<TNFAEpsilonTransition> EpsilonTransitions {
            get {
                // Return epsilon transition list.
                return _EpsilonTransitions;
            }
        }

        /// <summary>
        /// Compare this TNFAstate to the other, introducing a total ordering to NFA states by refering to their state IDs that
        /// are assigned during creation.
        /// </summary>
        /// <param name="other">State to compare against.</param>
        /// <returns>Comparison result, -1 if this is smaller, 1 if this is bigger, 0 if equal.</returns>
        public int CompareTo(TNFAState other) {
            // Compare identity against other.
            if( _ID < other._ID )
                // This is smaller.
                return -1;
            else if( _ID > other._ID )
                // This is bigger.
                return 1;

            // Equal.
            return 0;
        }

    }

    /// <summary>
    /// Helper class representing an epsilon transition.
    /// </summary>
    internal class TNFAEpsilonTransition {

        // Data.
        private TNFAState _Target;
        private ITNFATag _Tag;

        /// <summary>
        /// Initialize a new epsilon transition, which has no tag bound.
        /// </summary>
        /// <param name="target">Target this TNFA state points to.</param>
        public TNFAEpsilonTransition(TNFAState target) {
            // Empty epsilon transition.
            _Target = target;
        }

        /// <summary>
        /// Initialize a new epsilon transition, binding it to the specified tag.
        /// </summary>
        /// <param name="target">Target this TNFA state points to.</param>
        /// <param name="tag">Tag to assign to the transition.</param>
        public TNFAEpsilonTransition(TNFAState target, ITNFATag tag) {
            // Initialize epsilon transition with tag.
            Debug.Assert(tag != null, "Trying to assign NULL tag to transition");
            _Target = target;
            _Tag = tag;
        }

        /// <summary>
        /// Retrieve target of a standard transition.
        /// </summary>
        public TNFAState Target {
            get {
                // Return target.
                return _Target;
            }
        }

        /// <summary>
        /// Check whether this epsilon transition has an associated tag.
        /// </summary>
        public bool HasTag {
            get {
                // Return tag state.
                return _Tag != null;
            }
        }

        /// <summary>
        /// Tag value associated with this epsilon transition.
        /// </summary>
        public ITNFATag Tag {
            get {
                // Return tag.
                return _Tag;
            }
        }

    }

    /// <summary>
    /// Helper class representing an ordinary transition on a character range.
    /// </summary>
    internal class TNFATransition {

        // Data.
        private TNFAState _Target;
        private CharRange _Range;

        /// <summary>
        /// Create a new "standard" transition on the specified character range.
        /// </summary>
        /// <param name="target">Target this transition points to.</param>
        /// <param name="range">Character range on which this transition is taken.</param>
        public TNFATransition(TNFAState target, CharRange range) {
            // Store data.
            _Target = target;
            _Range = range;
        }

        /// <summary>
        /// Retrieve target of a standard transition.
        /// </summary>
        public TNFAState Target {
            get {
                // Return target.
                return _Target;
            }
        }

        /// <summary>
        /// Character range on which this transition is taken.
        /// </summary>
        public CharRange Range {
            get {
                // Return character range.
                return _Range;
            }
        }

    }

    /// <summary>
    /// Helper class used to store a complete TDFA state which contains one TNFA state information for each TNFA state contained
    /// in this set.
    /// </summary>
    internal class TNFAStateSet {

        // Data.
        private SortedDictionary<TNFAState, TNFAStateDescription> _States =
            new SortedDictionary<TNFAState, TNFAStateDescription>();
        private SortedDictionary<ITNFATag, SortedDictionary<int, int>> _AdaptTagIndex =
            new SortedDictionary<ITNFATag, SortedDictionary<int, int>>();
        private SortedDictionary<ITNFATag, int> _CreateTagIndex = new SortedDictionary<ITNFATag, int>();
        private int? _Hash;

        /// <summary>
        /// Initialize a new TDFA state from the specified beginning NFA state.
        /// </summary>
        public TNFAStateSet(TNFAState begin) {
            // Create the TDFA state.
            _States[begin] = new TNFAStateDescription(begin, new SortedDictionary<ITNFATag, int>());
            Closure(new SortedDictionary<ITNFATag, int>());
        }

        /// <summary>
        /// Helper constructor which initializes a new, empty TDFA state set. Used by TNFASetTransition.
        /// </summary>
        protected TNFAStateSet() {
            // No specific construction.
        }

        /// <summary>
        /// Deliver a list of states that are bound to this NFA state set.
        /// </summary>
        public IEnumerable<TNFAStateDescription> States {
            get {
                // Return states list in this state.
                return _States.Values;
            }
        }

        /// <summary>
        /// Fetch tag adaptations required on entering this state.
        /// </summary>
        public SortedDictionary<ITNFATag, SortedDictionary<int, int>> AdaptTagIndex {
            get {
                // Return tag index adaptations.
                return _AdaptTagIndex;
            }
        }

        /// <summary>
        /// Fetch tag index creations on entering this state.
        /// </summary>
        public SortedDictionary<ITNFATag, int> CreateTagIndex {
            get {
                // Return tag index creations on entering this state.
                return _CreateTagIndex;
            }
        }

        /// <summary>
        /// Build the closure on the current state set and normalize the set, creating appropriate tag adaptations.
        /// </summary>
        private void Closure(SortedDictionary<ITNFATag, int> nexttagidx) {
            // Initialize processing queue.
            Stack<TNFAStateDescription> toprocess = new Stack<TNFAStateDescription>(_States.Values);
            while( toprocess.Count > 0 ) {
                // Fetch state to process.
                TNFAStateDescription state = toprocess.Pop();
                foreach( TNFAEpsilonTransition trans in state.State.EpsilonTransitions ) {
                    // Check for tag on transition, and if present, assign new index.
                    SortedDictionary<ITNFATag, int> tags = state.Tags;
                    if( trans.HasTag ) {
                        // Need to copy tags; is a changed set.
                        tags = new SortedDictionary<ITNFATag, int>(tags);

                        // Fetch next tag index from next index map for set, or create if not present yet.
                        int nextidx;
                        if( !nexttagidx.TryGetValue(trans.Tag, out nextidx) )
                            nexttagidx[trans.Tag] = nextidx = 0;
                        tags[trans.Tag] = nextidx;
                    }

                    // Create new state and attach it to closure states (and to states to process) if it doesn't match existing
                    // state. We overwrite a transition inserted earlier when the newly created transition is a superset
                    // (see below) when the priority is equal, or if the priority reaching the new transition is lower.
                    TNFAStateDescription oldstate;
                    TNFAStateDescription newstate = new TNFAStateDescription(trans.Target, tags);
                    if( !_States.TryGetValue(trans.Target, out oldstate) ) {
                        // Insert/update state.
                        _States[trans.Target] = newstate;
                        toprocess.Push(newstate);
                    } else {
                        // Output tags.
                        foreach( KeyValuePair<ITNFATag, int> otag in oldstate.Tags )
                            Console.Write("{0},{1} ", otag.Key, otag.Value);
                        Console.Write("| ");
                        foreach( KeyValuePair<ITNFATag, int> ntag in newstate.Tags )
                            Console.Write("{0},{1} ", ntag.Key, ntag.Value);

                        // Check whether we are after.
                        bool isafter = oldstate.IsAfter(newstate);
                        Console.WriteLine("| first is after second: {0}", isafter);
                        if( isafter ) {
                            // Insert/update state.
                            _States[trans.Target] = newstate;
                            toprocess.Push(newstate);
                        }
                    }
                }
            }

            // Walk over states that were collected, building list of indexes that we use for each tag.
            SortedDictionary<ITNFATag, HashSet<int>> usedidx = new SortedDictionary<ITNFATag, HashSet<int>>();
            foreach( TNFAStateDescription state in _States.Values ) {
                foreach( KeyValuePair<ITNFATag, int> tag in state.Tags ) {
                    // Check whether hash set for tag is set up.
                    HashSet<int> usedidxs;
                    if( !usedidx.TryGetValue(tag.Key, out usedidxs) )
                        usedidx[tag.Key] = usedidxs = new HashSet<int>();

                    // Attach tag value to index map.
                    usedidxs.Add(tag.Value);
                }
            }

            // Check list of used tags for possible reordering/creation items.
            foreach( KeyValuePair<ITNFATag, HashSet<int>> tag in usedidx ) {
                // Initialize sorted list of tags (to possibly reorder, preserving the original sorting).
                List<int> used = new List<int>(tag.Value);
                used.Sort();

                // Check whether we need to add item at all to adaptations.
                SortedDictionary<int, int> adapt = null;
                int newtag = 0;
                if( used.Count <= used[used.Count - 1] ) {
                    // Initialize new adaptation list for item and create simple incremental ordering.
                    _AdaptTagIndex[tag.Key] = adapt = new SortedDictionary<int, int>();
                    foreach( int i in used ) {
                        // Check whether we would actually change the tag value.
                        if( i != newtag )
                            adapt[i] = newtag;
                        ++newtag;
                    }
                }

                // Check whether we need to add creation.
                int nextidx = nexttagidx[tag.Key];
                if( used[used.Count - 1] == nextidx )
                    _CreateTagIndex[tag.Key] = nextidx;
            }

            // Adapt elements of all tag maps that are set up by new tag adaptation.
            Dictionary<SortedDictionary<ITNFATag, int>, SortedDictionary<ITNFATag, int>> adapts =
                new Dictionary<SortedDictionary<ITNFATag, int>, SortedDictionary<ITNFATag, int>>();
            foreach( TNFAStateDescription state in _States.Values ) {
                // Check whether we already have a new adaptation set for this one.
                SortedDictionary<ITNFATag, int> oldtags = state.Tags;
                SortedDictionary<ITNFATag, int> newtags;
                if( adapts.TryGetValue(oldtags, out newtags) ) {
                    // Just set it to already adapted item.
                    state.Tags = newtags;
                    continue;
                }

                // Walk over the tags, updating them if appropriate.
                foreach( ITNFATag tag in oldtags.Keys ) {
                    // Only adapt those tags that have an adaptation in this step.
                    SortedDictionary<int, int> adapt;
                    if( _AdaptTagIndex.TryGetValue(tag, out adapt) ) {
                        // Check whether we've already copied tags. If not, do it now, and update current item.
                        if( newtags == null )
                            newtags = new SortedDictionary<ITNFATag, int>(oldtags);

                        // Fetch adaptation if appropriate.
                        int oldtag = oldtags[tag];
                        int newtag;
                        if( adapt.TryGetValue(oldtag, out newtag) )
                            // Has adaptation, store that.
                            newtags[tag] = newtag;
                        else
                            // Doesn't have adaptation, no store.
                            newtags[tag] = oldtag;
                    }
                }

                // Finalize new tags and insert it.
                if( newtags != null ) {
                    // Yes, changed something; store adaptation for tag set.
                    state.Tags = newtags;
                    adapts[oldtags] = newtags;
                } else
                    // Tag set stays the same, store equality transform (so we don't need to loop again).
                    adapts[oldtags] = oldtags;
            }
        }

        /// <summary>
        /// List all reachable base TDFA states (without closure being applied) that are reachable from this TDFA state with
        /// the corresponding character range that reaches them.
        /// </summary>
        /// <returns>Enumerator over the transition sets.</returns>
        public IEnumerable<TNFASetTransition> Reach() {
            // Fetch lists of transitions from states.
            List<CharRange> ranges = new List<CharRange>();
            List<TNFAStateDescription> states = new List<TNFAStateDescription>();
            foreach( TNFAStateDescription state in _States.Values ) {
                // Check whether this has a character transition.
                if( state.State.Transition != null ) {
                    // Attach ranges and state.
                    ranges.Add(state.State.Transition.Range);
                    states.Add(state);
                }
            }

            // Loop over the ranges, merging them.
            foreach( StateRange range in CharRange.GroupRanges(ranges) ) {
                // Initialize new transition range.
                TNFASetTransition trans = new TNFASetTransition(range.Range);
                SortedDictionary<ITNFATag, int> nexttagidx = new SortedDictionary<ITNFATag, int>();
                for( int i = 0; i < ranges.Count; ++i ) {
                    // Check whether state is contained in output.
                    if( range[i] ) {
                        // Attach the corresponding target state to this set (reusing the tag set, as it doesn't change).
                        TNFAState target = states[i].State.Transition.Target;
                        trans._States[target] = new TNFAStateDescription(target, states[i].Tags);

                        // Update list of largest tag Indices in the target state for all present tags.
                        int oldtag;
                        foreach( KeyValuePair<ITNFATag, int> tag in states[i].Tags )
                            if( !nexttagidx.TryGetValue(tag.Key, out oldtag) || tag.Value >= oldtag )
                                nexttagidx[tag.Key] = tag.Value + 1;
                    }
                }

                // Check whether target state has any content, and if so, yield it.
                if( trans._States.Count > 0 ) {
                    // Finalize closure and yield.
                    trans.Closure(nexttagidx);
                    yield return trans;
                }
            }
        }

        /// <summary>
        /// Function to calculate a hash code which identifies this TNFA state set.
        /// </summary>
        /// <returns>Hash code of the state set.</returns>
        public override int GetHashCode() {
            // Check whether hash has already been set up.
            if( !_Hash.HasValue ) {
                // Initialize hash code with states (in that sort order).
                int hash = 0;
                foreach( TNFAStateDescription state in _States.Values )
                    hash = ( ( hash << 5 ) | ( hash >> 27 ) ) ^ state.GetHashCode();

                // Store hash.
                _Hash = hash;
            }

            // Return hash.
            return _Hash.Value;
        }

        /// <summary>
        /// Compare two state sets for equivalence. This only compares the contained states and their marked tags, not the
        /// adaptations that are to be executed in this state. Those are independent of the state set.
        /// </summary>
        /// <param name="obj">Object to compare against.</param>
        /// <returns>Return true iff the two state sets are equal.</returns>
        public override bool Equals(object obj) {
            // Compare base data of other object.
            TNFAStateSet other = obj as TNFAStateSet;
            if( other == null || ( other._Hash.HasValue && _Hash.HasValue && other._Hash.Value != _Hash.Value ) ||
                _States.Count != other._States.Count )
                // Basic state equivalence not present; won't compare.
                return false;

            // Loop while fetching an element from either works.
            IEnumerator<KeyValuePair<TNFAState, TNFAStateDescription>>[] dicts =
                new IEnumerator<KeyValuePair<TNFAState, TNFAStateDescription>>[] {
                    _States.GetEnumerator(), other._States.GetEnumerator()
                };
            while( dicts[0].MoveNext() && dicts[1].MoveNext() )
                // Compare elements. We just need to compare the state descriptions, they contain all data.
                if( !dicts[0].Current.Value.Equals(dicts[1].Current.Value) )
                    return false;

            // When we get here, the comparison worked out as both sequences are equally long and first ran out.
            return true;
        }

    }

    /// <summary>
    /// Helper class to represent a TNFA state which binds an NFA state to a priority (last transition getting it there) and
    /// a set of tags that are assigned here, with indices in the tag map.
    /// </summary>
    internal class TNFAStateDescription {

        // Data.
        private TNFAState _State;
        private SortedDictionary<ITNFATag, int> _Tags;
        private int? _Hash;

        /// <summary>
        /// Initialize a new TNFA state bound to an NFA state, with the specified priority and the specified tags bound.
        /// </summary>
        /// <param name="state">State that this state description is for.</param>
        /// <param name="tags">Tags and their indices that are bound to this NFA state.</param>
        public TNFAStateDescription(TNFAState state, SortedDictionary<ITNFATag, int> tags) {
            // Store data.
            _State = state;
            _Tags = tags;
        }

        /// <summary>
        /// Fetch the associated NFA state.
        /// </summary>
        public TNFAState State {
            get {
                // Return attached NFA state.
                return _State;
            }
        }

        /// <summary>
        /// Fetch tag map of the current TDFA state.
        /// </summary>
        public SortedDictionary<ITNFATag, int> Tags {
            get {
                // Return tag map.
                return _Tags;
            }
            set {
                // Update tags.
                _Tags = value;
            }
        }

        /// <summary>
        /// Helper method to calculate a hash code for this state description.
        /// </summary>
        /// <returns>Returns a hash code that identifies this state description.</returns>
        public override int GetHashCode() {
            // Check whether hash has already been set up.
            if( !_Hash.HasValue ) {
                // Initialize hash with base data.
                int hash = _State.GetHashCode();
                foreach( KeyValuePair<ITNFATag, int> tag in _Tags ) {
                    // Attach key and hash.
                    hash = ( ( hash << 5 ) | ( hash >> 27 ) ) ^ tag.Key.GetHashCode();
                    hash = ( ( hash << 7 ) | ( hash >> 25 ) ) ^ tag.Value;
                }

                // Store hash.
                _Hash = hash;
            }

            // Return hash.
            return _Hash.Value;
        }

        /// <summary>
        /// Helper method to compare another object for equivalence with this object.
        /// </summary>
        /// <param name="obj">Object to compare against.</param>
        /// <returns>Return true iff the other object matches this object.</returns>
        public override bool Equals(object obj) {
            // Convert other and check basic criteria.
            TNFAStateDescription other = obj as TNFAStateDescription;
            if( other == null || other._State != _State ||
                ( _Hash.HasValue && other._Hash.HasValue && _Hash.Value != other._Hash.Value ) ||
                other._Tags.Count != _Tags.Count )
                return false;

            // Check tag equivalence.
            IEnumerator<KeyValuePair<ITNFATag, int>>[] dicts = new IEnumerator<KeyValuePair<ITNFATag, int>>[] {
                _Tags.GetEnumerator(), other._Tags.GetEnumerator()
            };
            while( dicts[0].MoveNext() && dicts[1].MoveNext() )
                // Compare single tag element in dictionary.
                if( dicts[0].Current.Key != dicts[1].Current.Key || dicts[0].Current.Value != dicts[1].Current.Value )
                    return false;

            // All compared equal, objects must be equal.
            return true;
        }

        /// <summary>
        /// Compare two TNFAStateDescription elements, returning whether the other TNFA state is a superset of this TNFA state.
        /// A TNFAStateDescription is a superset of another if it contains more elements or the tag indices that are set up
        /// for it are higher than for the other (i.e., the tags are later in the input stream).
        /// </summary>
        /// <param name="other">Set to compare against.</param>
        /// <returns>true iff other is a superset of this state description.</returns>
        public bool IsAfter(TNFAStateDescription other) {
            // Create iterators over the two elements.
            IEnumerator<KeyValuePair<ITNFATag, int>>[] dicts = new IEnumerator<KeyValuePair<ITNFATag, int>>[] {
                _Tags.GetEnumerator(), other._Tags.GetEnumerator()
            };
            while( true ) {
                // Fetch item from both dicts. If none were found in either, these two sets are equal.
                bool found0 = dicts[0].MoveNext();
                bool found1 = dicts[1].MoveNext();

                // Check whether we found both. If so, the tag value comparison decides which one we "didn't" find.
                if( found0 && found1 ) {
                    // Compare tags for precedence.
                    int cmp = dicts[0].Current.Key.CompareTo(dicts[1].Current.Key);
                    if( cmp < 0 )
                        // Ours has higher precedence, ignore value in second dict.
                        found1 = false;
                    else if( cmp > 0 )
                        // Other has higher precedence, ignore value in our dict.
                        found0 = false;
                    else {
                        // Tags are equal, decide based on tag value equivalence.
                        if( dicts[0].Current.Key.MinimizeMatch ) {
                            // Check whether we want to minimize; in case we do and have bigger value, we are worse.
                            if( dicts[0].Current.Value > dicts[1].Current.Value )
                                // We have the bigger value, so we are worse.
                                return true;
                            else if( dicts[0].Current.Value < dicts[1].Current.Value )
                                // We have the smaller value, so we are better.
                                return false;
                        } else if( dicts[0].Current.Value < dicts[1].Current.Value )
                            // Tag wants to be maximized and we are smaller, so we are worse.
                            return true;
                        else if( dicts[0].Current.Value > dicts[1].Current.Value )
                            // We have the bigger value and want maximize, so we are better.
                            return false;

                        // Couldn't decide; tag values are equal, so decide on next tag.
                        continue;
                    }
                } else if( !found0 && !found1 )
                    // Both dicts ran out, the tag sets are equal (we are not worse).
                    return false;

                // Check whether we found first.
                if( found0 )
                    // When we want to minimize tag, other has the "better" value (-1, no value assigned), otherwise us.
                    return dicts[0].Current.Key.MinimizeMatch;
                else
                    // When we want to minimize tag, we have the "better" value (-1, no value assigned), otherwise other.
                    return !dicts[1].Current.Key.MinimizeMatch;
            }
        }

    }

    /// <summary>
    /// Helper class to bind a TDFA state set to a transition which was taken to reach this state set.
    /// </summary>
    internal class TNFASetTransition : TNFAStateSet {

        // Data.
        private Range _Range;

        /// <summary>
        /// Initialize a new TDFA transition as an empty state set, bound to the specified character range.
        /// </summary>
        /// <param name="range">Character range that triggers this transition.</param>
        public TNFASetTransition(Range range) {
            // Store data.
            _Range = range;
        }

        /// <summary>
        /// Fetch character range transition is bound to.
        /// </summary>
        public Range Range {
            get {
                // Return character range this transition is bound to.
                return _Range;
            }
        }

    }

}
